yukicoder contest 369 B
解き方
※ ここに書く解き方は、解説に書かれている解き方と異なる この問題では、"con" という文字列の個数を求めているが、より一般に、正整数$ L に対して、長さ$ L の文字列が与えられたときに、その文字列を含む個数を求める問題を考える。
結論をまず述べると、これは次のように求めることができる。
次のような漸化式を満たす関数$ \mathrm{dp} を考える。ただし、$ a \% b は整数$ a を正整数$ b で割った余りを表す。
$ \mathrm{dp}(0,0) = 0 かつ $ 1 以上$ L 未満の任意の整数$ j について$ \mathrm{dp}(0,j) = 0
任意の非負整数$ i と$ 0 以上$ L 未満の任意の非負整数$ j について$ \mathrm{dp}(i+1, j) = \mathrm{dp}(i, (j-1) \% L) + 25 \times \mathrm{dp}(i, j)
このとき、求める値は$ \sum_{i = 0}^{N-1} \mathrm{dp}(i, L-1) \times 26^{N-i-1} である。よって$ O(NL) の計算量で計算可能である。
次に、この計算方法の正当性について述べる。
まず、文字列$ S の連続ではない部分列として、特定の文字列$ T を作ることができるかを調べるには、文字列$ S を先頭から見ていって、次に必要な$ T の文字を見つけたら、それを部分列に含めるようにすれば良い。
例えば、"cocoon" という文字列の部分列として"con" を作成する方法は何通りかあるが、次のように作成することを考える。
まず"con" の1文字目である'c' を探して"cocoon" を先頭から見ていくと1文字目にみつかるため、それを部分列に含める。
"cocoon" を1文字目まで見たので、次は2文字目からはじめて、"con" の2文字目である'o' を探す。すると2文字目に見つかる。
"cocoon" を2文字目まで見たので、次は3文字目からはじめて、"con" の3文字目である'n' を探す。すると6文字目に見つかる。
実は、文字列$ S の連続ではない部分列として、特定の文字列$ T を作ることができる場合は、上の方法で必ず作れることがわかる。
厳密な証明はここでは行わないが、順番に行う作業を期限までに終わらせるスケジュールを考えたときに、途中の作業を早く終わらせても、スケジュールが遅れることにはならないように、$ T の次の文字が早く見つかったなら、それを使っても後続の動作に影響はない。
さて、ここで最初の計算に立ち返り、この計算の意図を述べる。
$ \mathrm{dp}(i, j) という値は、長さが$ i の文字列のうち、個数を数えたい文字列の$ j 文字目まで見つかっているものの個数を意図している。
そして、上の漸化式は、$ i+1 番目の文字列が、個数を数えたい文字列の$ j+1 番目の文字かどうかの場合分けをイメージしている。
個数を数えたい文字列の$ j+1 番目の文字は$ 1 個しかないため、$ \mathrm{dp}(i, j) \times 1 を$ \mathrm{dp}(i, j+1) に足している。
個数を数えたい文字列の$ j+1 番目の文字ではない文字は$ 25 個あるため、$ \mathrm{dp}(i, j) \times 25 を$ \mathrm{dp}(i, j) に足している。
ただし、今回の問題では、個数を数えたい文字列が1つ含まれていることが確認できれば終わりということではないため、$ L 文字目まで見つけたら、どこまで見つけたかの情報を$ 0 にリセットしている。
※ 解説に書かれた方法と比較すると、この$ \mathrm{dp} の発想と、$ O(N^{2}) の解法の解説に書かれた$ \mathrm{dp} の発想は、ほとんど同じものである。ただし、こちらは$ L 文字ごとにリセットしているため、解説に書かれた$ \mathrm{dp} で$ j \% L が同じものを全て足して1つにまとめているイメージ
次に、最終的に求めたい値である$ \sum_{i = 0}^{N-1} \mathrm{dp}(i, L-1) \times 26^{N-i-1} の意図について述べる。
$ \mathrm{dp}(i, L-1) は、長さ$ i の文字列で、個数を数えたい文字列が最後の文字を除いて完成しているような状態である文字列の数である。
このような文字列の末尾に、個数を数えたい文字列の最後の文字を追加すると、それぞれの文字列で個数を数えたい文字列が1つ増える。
よって、このような文字列の数だけ最終的に求めたい値が増えることになるため、そのような文字列の数を各$ i について足している。
ただし、長さ$ i の文字列に1文字追加しただけでは、長さ$ N になるのに$ N-i-1 文字足りないため、それらも追加する必要がある。
どの文字を追加しても、$ i+1 番目の文字で、個数を数えたい文字列が1つ完成することは変わらないため、どの文字を追加しても良い。
よって、追加する文字の組み合わせとしてあり得るのは$ 26^{N-i-1} 通りあるので、それを掛けている。
解答例
下は上記の方法で解いたときの提出結果である。また、上記の提出の際に提出したソースコードをその下に転記する。
code: C
int main () {
int n = 0;
int res = 0;
long long ans = 0LL;
long long mod_num = 998244353LL;
long long pow263000 = {}; res = scanf("%d", &n);
for (int i = 1; i < n; i++) {
pow26i = (pow26i-1*26LL)%mod_num; }
for (int i = 0; i < n; i++) {
}
printf("%lld\n", ans%mod_num);
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_369_H
提出のURL 提出時刻 結果 備考
感想
この問題を解く方法として、上で述べた$ O(NL) の方法しか思いつかなかったため、制約が小さめなのを不思議に思っていた。
解説を見て、計算量が$ N^{2} のオーダーになる解き方があったのかと合点がいった。
そして$ O(N) の方法も全く思いついていなかったが、言われてみれば漸化式をみると毎回25倍するか1倍するかのどちらかなので、
$ N 回の遷移のうち、25倍する箇所を何個にするかを考えれば、確かに解けるんやね。
なんとなくプロフィールページをみてみたら、「ゆるふわポイント」が30の倍数でないのが気になって、それで一覧を見て気がついた。
私の提出が、この問題の最短時間になっていたんやね。ただ、みなさんとの差が1ms 程度なので、運良く誤差でそうなっただけのような。
今回の問題は$ L が小さいので差が出ないけれど、$ O(N) の解き方に比べて計算量が良くない解き方なのに良いのかという気分も。